function MyMap() {
  this.init()
}

MyMap.prototype.init = function () {
  // 散列表长度
  this.size = 0;

  // bucket 为散列表结构：数组 + 链表，初始化时每个链表的 next 指向头指针
  this.bucket = new Array(8).fill(0).map(() => {
    return {
      next: null
    }
  });

  // 记录头尾节点
  this.head = {
    next: null
  };
  this.tail = null;
};

MyMap.prototype.hash = function (key) {
  let index = 0;

  // 根据 key 的类型来给数据分类，返回指定的 index
  if (typeof key == "object") {
    index = 0;
  } else if (typeof key === "undefined") {
    index = 1;
  } else if (typeof key === "null") {
    index = 2;
  } else if (typeof key === "boolean") {
    index = 3;
  } else if (typeof key === "number") {
    // 给数字执行求余取模操作
    index = key % this.bucket.length;
  } else if (typeof key == "string") {
    for (let i = 0; i < key.length; i++) {
      // 求取字符串每个字符的 Unicode 编码之和
      index += key.charCodeAt(i);
    }
    // 给字符串 index 执行求余取模操作
    index = index % this.bucket.length;
  }

  return index;
}

MyMap.prototype.set = function (key, value) {
  // 根据 key 值获取到对应的链表下标，得到要操作的链表
  const index = this.hash(key);
  let listNode = this.bucket[index];

  let flag = false;
  // 遍历链表，在链表尾部追加数据
  while (listNode.next) {
    // 如果有 key 存在，执行更新操作，并返回自身对象
    if (listNode.next.key === key) {
      listNode.next.value = value;

      // return this;
      flag = true;
      break;
    }

    // 没找到链表向下移动
    listNode = listNode.next;
  }

  // 如果存在，更新 head 节点中的 value
  if (flag) {
    listNode = this.head;
    while (listNode.next) {
      if (listNode.next.key === key) {
        listNode.next.value = value;
        return this;
      }

      listNode = listNode.next;
    }
  }

  const node = {
    key,
    value,
    next: null
  };
  // 如果遍历完都没有找到，就执行新增操作
  listNode.next = node;

  // 给头尾节点赋值，记录散列表的顺序
  if (this.size === 0) {
    this.head.next = node
    this.tail = this.head.next;
  } else {
    this.tail.next = node
    this.tail = this.tail.next;
  }

  this.size++;
  return this;
};

MyMap.prototype.get = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  // 遍历链表，找到指定的key并返回value，没有找到就返回undefined
  while (listNode.next) {
    if (listNode.next.key === key) {
      return listNode.next.value;
    }

    // 没找到链表向下移动
    listNode = listNode.next;
  }

  return undefined;
};

MyMap.prototype.has = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  // 遍历链表，找到指定的key，如果有返回true，反之返回false
  while (listNode.next) {
    if (listNode.next.key === key) {
      return true;
    }

    // 没找到链表向下移动
    listNode = listNode.next;
  }

  return false;
};

MyMap.prototype.delete = function (key) {
  const i = this.hash(key);
  let listNode = this.bucket[i];

  let flag = false;
  // 遍历链表，找到指定的key，如果存在改变链表next指向同时改变head节点中的next指向并返回true，反之返回false
  while (listNode.next) {
    if (listNode.next.key === key) {
      listNode.next = listNode.next.next;
      this.size--;

      // return true;
      flag = true;
      break
    }

    // 没找到链表向下移动
    listNode = listNode.next;
  }

  if (flag) {
    listNode = this.head;
    while (listNode.next) {
      if (listNode.next.key === key) {
        listNode.next = listNode.next.next;
        break;
      }

      listNode = listNode.next;
    }
  }

  return flag;
};

MyMap.prototype.clear = function () {
  this.init();
};

MyMap.prototype.entries = function* () {
  // for (let i = 0; i < this.bucket.length; i++) {
  //   let listNode = this.bucket[i];

  //   while (listNode.next) {
  //     if (listNode.next.key) {
  //       yield [listNode.next.key, listNode.next.value];
  //     }

  //     listNode = listNode.next;
  //   }
  // }

  let listNode = this.head.next;

  // 从头节点开始按照顺序遍历
  while (listNode) {
    if (listNode.key) {
      yield [listNode.key, listNode.value];
    }

    listNode = listNode.next;
  }
};

MyMap.prototype.values = function* () {
  // for (let i = 0; i < this.bucket.length; i++) {
  //   let listNode = this.bucket[i];

  //   while (listNode.next) {
  //     if (listNode.next.key) {
  //       yield listNode.next.value;
  //     }

  //     listNode = listNode.next;
  //   }
  // }

  let listNode = this.head.next;

  // 从头节点开始按照顺序遍历
  while (listNode) {
    if (listNode.value) {
      yield listNode.value;
    }

    listNode = listNode.next;
  }
};

MyMap.prototype.keys = function* () {
  // for (let i = 0; i < this.bucket.length; i++) {
  //   let listNode = this.bucket[i];

  //   while (listNode.next) {
  //     if (listNode.next.key) {
  //       yield listNode.next.key;
  //     }

  //     listNode = listNode.next;
  //   }
  // }

  let listNode = this.head.next;

  // 从头节点开始按照顺序遍历
  while (listNode) {
    if (listNode.key) {
      yield listNode.key;
    }

    listNode = listNode.next;
  }
};

MyMap.prototype[Symbol.iterator] = MyMap.prototype.entries; //默认遍历器接口，for of使用

// forEach(fn, context)方法
MyMap.prototype.forEach = function (fn, context = this) {
  // for (let i = 0; i < this.bucket.length; i++) {
  //   let listNode = this.bucket[i];

  //   while (listNode.next) {
  //     if (listNode.next.key) {
  //       fn.call(context, listNode.next.value, listNode.next.key);
  //     }

  //     listNode = listNode.next;
  //   }
  // }

  let listNode = this.head.next;

  // 从头节点开始按照顺序遍历
  while (listNode) {
    if (listNode.key) {
      fn.call(context, listNode.value, listNode.key);
    }

    listNode = listNode.next;
  }
};

const map = new MyMap();

map.set('0', 'foo');
map.set(1, 'bar');
// map.set(1, 'bar2');
map.set({}, "baz");

console.log('get 0', map.get(0));
console.log('get 1', map.get(1));

console.log('has 0', map.has(0));
console.log('has 1', map.has(1));

// console.log('delete "0"', map.delete('0'));

const iterator = map.entries();
console.log(iterator.next().value);
console.log(iterator.next().value);
console.log(iterator.next().value);

const iterator1 = map.values();
console.log(iterator1.next().value);
console.log(iterator1.next().value);
console.log(iterator1.next().value);

const iterator2 = map.keys();
console.log(iterator2.next().value);
console.log(iterator2.next().value);
console.log(iterator2.next().value);

function logMapElements(value, key, map) {
  console.log(`m[${key}] = ${value}`);
}
map.forEach(logMapElements);

console.log(map);
